home *** CD-ROM | disk | FTP | other *** search
/ Spanish Scene 1 / SpanishScene1.iso / spanish pack n°1 by llfb / revistas / fanzine / fanzine01.dms / fanzine01.adf / 40 < prev    next >
Text File  |  1977-12-31  |  10KB  |  277 lines
  1.  
  2.  ----------------------------------------------------------------------------
  3.  
  4.    T E C N I C A S   D E  I N T E L I G E N C I A   A R T I F I C I A L
  5.  
  6.                   * INTRODUCCION A LA TEORIA DE GRAFOS   *
  7.  
  8.  ----------------------------------------------------------------------------
  9.  
  10.    Curso escrito por Warlord
  11.  
  12.    Mi intención con este semi-cursillo es hacer llegar a todos,de una  forma
  13.   sencilla y amena varias técnicas relacionadas con la Int. Artificial, poco
  14.   utilizadas generalmente por los programadores. Intentaré dar en cada caso,
  15.   algoritmos en C de cada una de estas técnicas. Si no  sabéis C, os  remito
  16.   al curso de esta revista. ¡Por cierto!, algunos de estos pseudocódigos  en
  17.   C, no  he  probado  si  funcionan  correctamente.  Quiero  decir,  que  el
  18.   algoritmo está bien escrito, pero el programa en C puede tener algún error
  19.   en el tipo de variables y cosas  así, que se pueden arreglar fácilmente.
  20.  
  21.   
  22.    El problema de grafos que aquí os planteo es tan sólo una breve, muy breve
  23.   explicación sobre este apasionante mundo: Grafos, programación dinámica ...
  24.   temas que escapan al conocimiento del usuario medio.Posiblemente, este tema
  25.   no interese a mucha gente,pero me contentaría con que interesara a una sóla
  26.   persona.Podéis dirigir vuestras cartas al apdo 232,San Fernando 11100,Cádiz
  27.  
  28.    Mi contacto con la IA (inteligencia artificial), fué ya hace mucho tiempo
  29.   cuando comencé a desarrollar un juego de estrategia. El problema que se me
  30.   planteaba, era el siguiente:
  31.  
  32.    Disponía de un mapa de Europa con aproximadamente unos  30  países.  Cada
  33.   país era controlado de forma independiente por el  ordenador, a  excepción
  34.   de España, que lo controlaba el jugador. Con el paso del  tiempo, un  país
  35.   conquistaba  a otros vecinos. Se  planteaba  entonces el problema de tener
  36.   inactivos a los ejércitos en un país. El ordenador debía entonces detectar
  37.   cuando debía mover ejércitos de un país a otro, y  como  moverlos  de  una
  38.   forma óptima, de manera que pasaran por el menor número de países posible,
  39.   pues  esto supondría un mayor coste. La solución lógica a estos  problemas
  40.   viene a través de los grafos. 
  41.  
  42.   ¿Pero qué es un grafo?
  43.  
  44.    Un grafo es un conjunto formado por unos puntos llamados nodos,y líneas
  45.   que comunican un nodo con otro, llamados caminos.
  46.  
  47.  
  48.      O------O--O   O   = Vértices
  49.     /      /  /    -,/ = Caminos de un vértice a otro
  50.    O------O--/
  51.  
  52.   UN BONITO EJEMPLO:
  53.   -----------------
  54.  
  55.  
  56.    ¿Quién no ha visto en algún pasatiempo eso de recorrer un dibujo sin reco-
  57.   rrer dos veces la misma linea?. Si, por ejemplo:
  58.  
  59.  
  60.                O
  61.              /   \         Es el típico dibujo de la casita. ¿Como recorrer
  62.             /     \       todo el dibujo sin pasar dos veces por la misma 
  63.            O¯¯¯¯¯¯¯O      línea?. Este problema, es uno típico de grafos. Los
  64.            | \   / |      vértices son los "O" y las líneas los arcos.
  65.            |  \ /  |
  66.            |   /   |
  67.            |  / \  |
  68.            | /   \ |
  69.            |/     \|
  70.            O¯¯¯¯¯¯¯O
  71.  
  72.    Por cierto, para aquellos que les interese: para saber si un problema de
  73.   este tipo tiene solución, hay  que fijarse en los  vértices. Miramos  las
  74.   líneas (arcos) que llegan a  cada uno, y apuntamos aquellos  en que  esta
  75.   cantidad de líneas es impar.
  76.  
  77.    En nuestro ejemplo: Del vértice superior llegan dos líneas (Par)
  78.   Como es par, no nos vale para nada.
  79.  
  80.   En los dos siguientes, llegan 4 líneas. También par
  81.  
  82.   En los dos inferiores, llegan ¡3 líneas!, ¡Impar!. Tenemos dos vertices
  83.   impares.
  84.  
  85.    Una vez hecho esto, puede ocurrir:
  86.  
  87.   - Que no haya ningún vértice "con líneas impares". Si esto ocurre, el pro-
  88.   blema se puede hacer empezando desde cualquier vértice y acabando en cual-
  89.   quier otro
  90.  
  91.   - Que haya exactamente 2 vértices " con líneas impares ", como en nuestro
  92.   ejemplo. El problema tiene solución. Pero hay que empezar en uno de estos
  93.   vértices y necesariamente  acabar en el otro. En  nuestro ejemplo, habría
  94.   que empezar en uno de los dos de abajo y acabar en el otro
  95.  
  96.   - Que no pase nada de lo de antes. El problema no tiene solución.
  97.  
  98.   ¿Interesante, verdad?
  99.  
  100.   ALGUNOS EJEMPLOS MAS SERIOS:
  101.   ---------------------------
  102.  
  103.    Supongamos que deseamos ir desde Cádiz hasta  Barcelona. Las rutas  son
  104.   múltiples y variadas. Nuestra intención seria viajar, haciendo el mínimo
  105.   número de kilómetros.
  106.  
  107.    La representación y solución de  este problema es  bien fácil  mediante
  108.   grafos. Representamos Cádiz, como el  vértice 1. A  las  ciudades  entre
  109.   ella  y Barcelona, por donde pasen carreteras les vamos dando el  nombre
  110.   de otros vértices: 2,3,4.... hasta llegar a Barcelona.Unimos cada ciudad
  111.   por el camino correspondiente. La  distancia de una ciudad a otra, sería
  112.   el costo para trasladarse de una ciudad a otra. Asi, seriá:
  113.  
  114.             
  115.  
  116.                             4 (linares)
  117.                            O
  118.                             \    O 3 (Córdoba)
  119.                              \  / Costo=130 Km
  120.                               |/
  121.                               O Vertice 2 (Sevilla)
  122.                               |
  123.                               | Costo=153 Km
  124.                               |
  125.                               O Vertice 1 (Cádiz)
  126.  
  127.                    y así sucesivamente. ¿Fácil no?
  128.  
  129.     Supongamos entonces que Cádiz es el vértice 1,y Barcelona el 45.
  130.    
  131.     Definimos una tabla T(45,45),donde T(i,j) va a significar la distancia
  132.    del vértice (ciudad en este caso) i a la j.
  133.  
  134.     Así por ejemplo: T(1,1)=0 distancia de Cadiz a Cádiz=0
  135.                      T(1,2)=T(2,1)=153 (distancia de Cádiz a Sevilla)
  136.  
  137.     Nuestra intención es hallar el mínimo de estas distancias
  138.  
  139.     Si por ejemplo Madrid fuera el vértice 13, T(1,13) no debería existir
  140.    pues no hay comunicación directa entre ambas ciudades.Es decir,si hay de
  141.    Cadiz a Sevilla,de Sevilla a Córdoba y de Córdoba a Madrid.Pero no direc-
  142.    tamente.Así,definimos todas estas como un número grande,de manera que en
  143.    la solución,esta carretera no aparezca.
  144.  
  145.     Por ejemplo,T(1,13)=99999999999,de esta forma este camino no aparecería
  146.    en la solución,pues si T(1,13) fuese 0,aparecéria seguro en la solución,
  147.    lo cual sería contraproducente.
  148.  
  149.  
  150.     RESOLUCION DE GRAFOS:
  151.     --------------------
  152.  
  153.      El siguiente pseudocódigo resuelve este problema.
  154.  
  155.      Supongamos que queremos hallar el camino más corto del vértice 1 al N
  156.     Definimos f(i)=camino más corto del vertice i al N
  157.     La solución deseada sería entonces f(1)
  158.      
  159.      main()
  160.      {
  161.      for (i=2,i<=N,i++) v(i)=t[1,i];
  162.      T={2,....N}
  163.      While (T!=Ø){            (Ø=conjunto vacío)
  164.       v[i]=min(v[j],j en T);
  165.       T=T-{i}
  166.       while (j en T) v[j]=min(v[j],v[i]+t[i,j]);
  167.       }
  168.      }
  169.  
  170.       Una vez finalizado,obtenemos que v[i]=f(i),con lo cual v[1] sería la
  171.      solución
  172.  
  173.    Un ejemplo concreto:
  174.       
  175.            2                        5   
  176.            O------------------------O--/------------O 7
  177.           / \                      /  /              \
  178.          /   \    4               /  /   8            \
  179.       1 O     ----O--------------/---    O------------ O 9
  180.          \        |_____________________/|            /
  181.           \       |                      |           /
  182.            \       --------------------|/           /
  183.           3 O--------------------------O------------
  184.                                        6  
  185.       (perdonar el dibujo,es difícil hacerlo mejor)
  186.  
  187.   Llamando como antes t(i,j)=distancia del vértice i al j:
  188.  
  189.       t(1,2)=1    t(1,3)=2  t(3,6)=4  t(4,5)=4  t(4,6)=3   t(5,7)=7
  190.       t(2,5)=12   t(3,4)=3  t(2,4)=6  t(4,8)=7  t(4,7)=15  t(6,8)=7
  191.  
  192.       t(6,9)=15   t(7,9)=4  t(8,9)=10
  193.  
  194.      El resto no existe (ie,se les dá un valor alto)
  195.      Os recomiendo lo dibujéis en un papel
  196.  
  197.       ¿Cómo se resuelve?
  198.  
  199.   En el programa anterior,la línea clave es:  
  200.  
  201.      while (j en T) v[j]=min(v[j],v[i]+t[i,j]);
  202.  
  203.      f(i)=camino más corto de i a 9
  204.  
  205.   Según el programa anterior, f(i) es pues:
  206.  
  207.      f(i)=min (f(j)+t[i,j])
  208.  
  209.   La idea es empezar con f(9):
  210.  
  211.     f(9)=f(j)+t[j,9] ,donde j son los vértices (nodos) antecesores de 9:
  212.       
  213.     f(9)=min (f(7)+3,f(8)+10,f(6)+15)
  214.  
  215.   Necesitamos ir hallando ahora f(7),f(8) y f(6) recurrentemente:
  216.  
  217.     f(7)=min(f(5)+7,f(5)+15)
  218.     f(8)=min(f(4)+7,f(6)+7)
  219.     f(6)=min(f(4)+3,f(3)+4)
  220.  
  221.    Ahora necesitamos f(4),f(5)....Aplicamos de nuevo lo mismo y así llega-
  222.   mos a f(1).Una vez conocido f(1),conocer el resto es inmediato.
  223.  
  224.    Si lo hacéis veréis que la menor distancia a recorrer es a través de los
  225.   nodos:
  226.  
  227.      1 --> 3 --> 4  --> 5 --> 7 --> 9
  228.  
  229.    Desde luego es una forma interesante  de  resolver un grafo. Sin embargo,
  230.   no sería aplicable al primer ejemplo, el del mapa de Europa.Este algoritmo
  231.   nos ha dicho el algoritmo más corto del primer nodo del grafo a otro nodo
  232.   cualquiera. Pero en el ejemplo del juego de estrategia nos interesa el coste
  233.   del camino más corto  entre  cualquier  par  de  países, es  decir,  entre
  234.   cualesquiear par de nodos.
  235.    
  236.    Para resolver este problema podemos utilizar el algoritmo de Floyd:
  237.  
  238.   ALGORITMO DE FLOYD:
  239.   ------------------
  240.  
  241.    Para ello dimensionaremos una matriz L, de tamaño NxN (N=Número de vérti-
  242.   ces o nodos),y cuyos elementos van a tener el minimo coste entre todos los
  243.   costes de los caminos que unen los nodos i,j.El algoritmo no puede ser más 
  244.   sencillo. He aquí el pseudocódigo:
  245.  
  246.   /* Asignación de variables*/
  247.  
  248.   for (i=1,i<=N,i++);
  249.   {
  250.    for (j=1,j<=N,j++);
  251.    {
  252.    l(i,j)= | longitud del camino que une los nodos (i,j)
  253.            | 99999999999 en otro caso (de que no exista)
  254.    }
  255.   }
  256.   
  257.   /* Programa principal*/
  258.   
  259.   for (i=1,i<=N,i++);
  260.   {
  261.    for (j=1,j<=N,j++);
  262.    {
  263.     for (k=1,k<=N,k++);
  264.     {
  265.     l(i,j)=min(l(i,j),l(i,k)+l(k,j);
  266.     }
  267.    }
  268.   }
  269.  
  270.    Al final cada elemento l(i,j) tendrá el mínimo costo(es decir,la mínima 
  271.   longitud) de los caminos que unen i con j.Así pues, si queremos ir del
  272.   país 4 al 10, la mínima distancia a cubrir se encuentra en l(4,10).
  273.  
  274.    Por hoy,ya está bien. Espero que estas rutinas os sean de utilidad,y si
  275.   es así, espero vuestras cartas y comentarios.Hasta la próxima...
  276.  
  277.